import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test {
    //验证二叉搜索树
    public int flag = 0;
    //int rootval = root.val;
    public boolean isValidBST(TreeNode root) {
        int rootval = root.val;
        preOrder(root,rootval);
        return flag==0?true:false;
    }
    //public int rootval = root.val;
    private void preOrder(TreeNode root,int key){
        if(root==null) return ;
        if(root.left!=null && root.left.val>= root.val ){
            flag = 1;
            return;
        }
        if(root.left!=null && root.left.val>= key){
            flag = 1;
            return;
        }
        if(root.right!=null && root.right.val <= root.val ){
            flag = 1;
            return;
        }if(root.right!=null && root.right.val <= key){
            flag = 1;
            return;
        }
        preOrder(root.left,key);
        preOrder(root.right,key);
    }


    //统计好节点的个数
    Map<Integer, List<Integer>> reachMap = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    int res = 0;

    public int countGoodNodes(int[][] edges) {
        // bulid trees
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            List<Integer> fList = reachMap.getOrDefault(from, new ArrayList<>());
            fList.add(to);
            reachMap.put(from, fList);
            List<Integer> tList = reachMap.getOrDefault(to, new ArrayList<>());
            tList.add(from);
            reachMap.put(to, tList);
        }
        // calc children
        visited.add(0);
        getChildren(0);
        return res;
    }

    public int getChildren(int root) {
        int cnt = 1;
        Set<Integer> childrenCntSet = new HashSet<>();
        for (int next : reachMap.get(root)) {
            if (!visited.contains(next)) {
                visited.add(next);
                int childrenCnt = getChildren(next);
                cnt += childrenCnt;
                childrenCntSet.add(childrenCnt);
            }
        }
        if (childrenCntSet.size() <= 1) {
            res++;
        }
        return cnt;
    }
}
